
import time,resource,math,os

INF = 10e10

def length(worker:list,task:list)->float:#求两个点的长度
    distance = (worker[2]-task[2])**2+(worker[3]-task[2])**2
    distance = pow(distance,1/2)
    return distance

def length2(worker:list,task:list)->float:#求两个点的长度,不开方的
    distance = (worker[2]-task[2])**2+(worker[3]-task[3])**2
    return distance

def satisfyLoc(worker:list,task:list)->bool:#验证任务与工作者之间是否符合活动范围内
    if length2(worker,task) > worker[4]*worker[4]:
        return False
    return True

def satifyTime(worker:list,task:list)->bool:#检查是否满足时间要求
    if (worker[0] < task[4] and task[0] < worker[6]) is False:
        return False
    return True

def satify(worker:list,task:list)->bool:#检查是否满足
    if satifyTime(worker,task) and satisfyLoc(worker,task):
        return True
    return False
    
def calcCost(worker:list,task:list)->float:
    if satisfyLoc(worker,task) and satifyTime(worker,task):
        return worker[7]*task[5]
    else:
        return 0.0

def dcmp(a:float,b:float)->bool:
    return math.isclose(a,b,rel_tol=1e-6)
def dcmp(a:float)->bool:
    return abs(a)<1e-6

class KM:
    def __init__(self,curTime,workerlist,tasklist):
        self.curTime = curTime
        self.workerlist = workerlist
        self.tasklist = tasklist
        self.wsize = len(workerlist)
        self.tsize = len(tasklist)
        self.slacks = []
        self.weight = []
        self.lx = []
        self.ly = []
        self.xy = []
        self.yx = []
        self.visitx = []
        self.visity = []
        
        
    def build(self,flag):
        if flag:#一般情况需要左边的节点少于右边节点，因为我选择右边节点开始遍历，如果右边节点多余左边节点会出现完全匹配时候无法退出dfs
            self.lx = [0.0 for i in range(self.wsize)]
            self.ly = [0.0 for i in range(self.tsize)]
            self.xy = [-1 for i in range(self.wsize)]
            self.yx = [-1 for i in range(self.tsize)]
            self.visitx = [False for i in range(self.wsize)]
            self.visity = [False for i in range(self.tsize)]
            for x in range(self.wsize):
                temp = []
                for y in range(self.tsize):
                    u = calcCost(self.workerlist[x],self.tasklist[y])
                    temp.append(u)
                    self.lx[x] = max(u,self.lx[x])
                self.weight.append(temp)
                    
        else:
            self.lx = [0.0 for i in range(self.tsize)]
            self.ly = [0.0 for i in range(self.wsize)]
            self.xy = [-1 for i in range(self.tsize)]
            self.yx = [-1 for i in range(self.wsize)]
            self.visitx = [False for i in range(self.tsize)]
            self.visity = [False for i in range(self.wsize)]
            for x in range(self.tsize):
                temp = []
                for y in range(self.wsize):
                    u = calcCost(self.workerlist[y],self.tasklist[x])
                    temp.append(u)
                    self.lx[x] = max(u,self.lx[x])
                self.weight.append(temp)
      
    def success(self,flag):
        #识别并删除成功匹配的
        utility = 0.0
        matchNum = 0
        removeWorkers = [False for i in range(self.wsize)]
        removeTasks = [False for i in range(self.tsize)]
        if flag:
            for w,t in enumerate(self.xy):
                if t!=-1:
#                     u = self.weight[w][t]
                    u1 = calcCost(self.workerlist[w],self.tasklist[t])
#                     if u!=u1:
#                         print(u,u1)
                    if u1 > 0.0:#匹配成功
                        utility += u1
                        removeWorkers[w]=True
                        removeTasks[t]=True
                        matchNum += 1
        else:
            for t,w in enumerate(self.xy):
                if w!=-1:
#                     u = self.weight[t][w]
                    u1 = calcCost(self.workerlist[w],self.tasklist[t])
#                     if u!=u1:
#                         print(u,u1)
                    if u1 > 0.0:
                        utility += u1
                        removeWorkers[w]=True
                        removeTasks[t]=True
                        matchNum += 1
        #识别未匹配成功的，并删除超时的众包对象
        wt = []
        tt = []
        for w,flag in enumerate(removeWorkers):
            worker = self.workerlist[w]
            if flag==False and worker[6] >= self.curTime:
                wt.append(worker)
        
        for t,flag in enumerate(removeTasks):
            task = self.tasklist[t]
            if flag==False and task[4] >= self.curTime:
                tt.append(task)

        return [utility,wt,tt,matchNum]
    
    def dfs1(self,x:int)->bool:
        self.visitx[x] = True
        for y,flag in enumerate(self.visity):
            if flag:
                continue
#             temp = self.lx[x] + self.ly[y] - self.weight[x][y]
            temp = self.lx[x] + self.ly[y] - calcCost(self.workerlist[x],self.tasklist[y])
            if dcmp(temp):
                self.visity[y] = True
                if self.yx[y] == -1 or self.dfs1(self.yx[y]):
                    self.xy[x] = y
                    self.yx[y] = x
                    return True
            else:
                self.slacks[y] = min(self.slacks[y],temp)###
        return False 
    
    def dfs2(self,x:int)->bool:
        self.visitx[x] = True
        for y,flag in enumerate(self.visity):
            if flag:
                continue
#             temp = self.lx[x] + self.ly[y] - self.weight[x][y]
            temp = self.lx[x] + self.ly[y] - calcCost(self.workerlist[y],self.tasklist[x])
            if dcmp(temp):
                self.visity[y] = True
                if self.yx[y] == -1 or self.dfs2(self.yx[y]):
                    self.xy[x] = y
                    self.yx[y] = x
                    return True
            else:
                self.slacks[y] = min(self.slacks[y],temp)###
        return False 
    def match(self):
        ans = [0,[],[],0]#效用，未匹配工作者，未匹配任务，匹配成功数
        wtflag = False
        
        if self.wsize <= self.tsize:#工作者作为左边节点
            if self.wsize == 0 or self.tsize == 0:
                ans[1] = self.workerlist
                ans[2] = self.tasklist
                return ans
            wtflag = True
            self.build(wtflag)
            for x in range(self.wsize): 
                self.slacks = [INF for i in range(self.tsize)]###
                while True:
                    self.visitx = [False for i in range(self.wsize)]
                    self.visity = [False for i in range(self.tsize)]
                    self.slack = INF
                    #wsize<tsize
                    if self.dfs1(x):
                        break

                    #更新访问过的节点, 因为self.wsize <= self.tsize，这里还可以优化加速
                    mm = INF###
                    for i,flag in enumerate(self.visity):###
                        if flag == False:###
                            mm = min(self.slacks[i],mm)###
                    for i,flag in enumerate(self.visitx):
                        if flag:
                            self.lx[i] -= mm###
                    for i,flag in enumerate(self.visity):
                        if flag:
                            self.ly[i] += mm###
                        else:###
                            self.slacks[i] -= mm###
            ans = self.success(wtflag)#工作者左边
            return ans

        else:#任务作为左边节点
            if self.wsize == 0 or self.tsize == 0:
                ans[1] = self.workerlist
                ans[2] = self.tasklist
                return ans
            wtflag = False
            self.build(wtflag)
            for x in range(self.tsize):
                self.slacks = [INF for i in range(self.wsize)]###
                while True:
                    self.visitx = [False for i in range(self.tsize)]
                    self.visity = [False for i in range(self.wsize)]
                    self.slack = INF
                    if self.dfs2(x):
                        break
                    #更新访问过的节点, 因为self.wsize > self.tsize，这里还可以优化加速
                    mm = INF###
                    for i,flag in enumerate(self.visity):###
                        if flag == False:###
                            mm = min(self.slacks[i],mm)###
                            
                    for i,flag in enumerate(self.visitx):
                        if flag:
                            self.lx[i] -= mm###
                    for i,flag in enumerate(self.visity):
                        if flag:
                            self.ly[i] += mm###
                        else:###
                            self.slacks[i] -= mm###
            ans = self.success(wtflag)#任务左边
            return ans
        
workers = []
tasks = []
queue = []
def readData(fileName):
    with open(fileName,'r') as f:
        data = f.readlines()
        first = data[0].strip("\n").split(" ")
        workerNum = int(first[0])
        taskNum = int(first[1])
        utilityMax = int(first[2])
        totalNum = int(first[3])
        for i in range(1,len(data)):
            node = data[i].strip("\n").split(" ")
            if node[1]=='w':
                node[0]=int(node[0])#到达时间
                node[2]=float(node[2])#纬度
                node[3]=float(node[3])#经度
                node[4]=float(node[4])#半径
                node[5]=int(node[5])#能力
                node[6]=int(node[6])+node[0]#停留的时间
                node[7]=float(node[7])#接受率
                if len(node) < 9:#最后一个用来记录等待多久匹配
                    node.append(0)
                else:
                    node[8] = 0
                workers.append(node)
            else:
                node[0]=int(node[0])#到达时间
                node[2]=float(node[2])#纬度
                node[3]=float(node[3])#经度
                node[4]=int(node[4])+node[0]#停留的时间
                node[5]=float(node[5])#支付的报酬
                if len(node) < 7:
                    node.append(0)
                else:
                    node[6] = 0
                tasks.append(node)
            queue.append(node)
    return workerNum,taskNum,utilityMax,totalNum

def selectTask(worker,taskList,curTime):
    maxCost = 0.0
    tindex = -1
    for i,task in enumerate(taskList):
        tempCost = calcCost(worker,task)
        if tempCost > maxCost and worker[6] >= curTime and task[4] >= curTime:
            maxCost = tempCost
            tindex = i
    if tindex != -1:#匹配成功，删除成功匹配的任务
        taskList.pop(tindex)
    return maxCost
def selectWorker(task,workerList,curTime):
    maxCost = 0.0
    windex = -1
    for i,worker in enumerate(workerList):
        tempCost = calcCost(worker,task)
        if tempCost > maxCost and worker[6] >= curTime and task[4] >= curTime:
            maxCost = tempCost
            windex = i
    if windex != -1:#匹配成功，删除成功匹配的工作者
        workerList.pop(windex)
    return maxCost

def removeDeadline(mworkers:list,mtasks:list,curTime):
    saveWs = []
    saveTs = []
    for worker in mworkers:
        if worker[6] >= curTime:
            saveWs.append(worker)
    for task in mtasks:
        if task[4] >= curTime:
            saveTs.append(task)
    return saveWs,saveTs
    

def TGOA_OP(totalNum):
    mworkers = []
    mtasks = []
    curTime = 0
    utility = 0.0
    arriveNum = 0
    matchNum = 0
    k = int(totalNum*0.5)
    batch = []
    for index,item in enumerate(queue):
        batch.append(item)
        curTime = item[0]
        if index == len(queue)-1 or curTime != queue[index+1][0]:
            #删除超时的
            mworkers,mtasks = removeDeadline(mworkers,mtasks,curTime)
            if arriveNum < k:#第一阶段
                for node in batch:
                    crowType = node[1]
                    if crowType == "w":#如果是工作者
                        cap = node[5]
                        for w in range(cap):
                            utemp = selectTask(node,mtasks,curTime)
                            if utemp != 0.0:#匹配成功
                                utility += utemp
                                matchNum += 1
                            else:#未匹配成功则进入等待队列
                                mworkers.append(node)
                            arriveNum += 1#标记到达了几个众包参与者
                    else:
                        utemp = selectWorker(node,mworkers,curTime)
                        if utemp != 0.0:#匹配成功
                            utility += utemp
                            matchNum += 1
                        else:
                            mtasks.append(node)
                        arriveNum += 1#标记到达了几个众包参与者
                
            else:#第二阶段
                for node in batch:
                    crowType = node[1]
                    if crowType == "w":
                        cap = node[5]
                        for w in range(cap):
                            mworkers.append(node)
                            arriveNum += 1#标记到达了几个众包参与者
                    else:
                        mtasks.append(node)
                        arriveNum += 1 #标记到达了几个众包参与者
                assignment = KM(curTime,mworkers,mtasks)
                utemp,mworkers,mtasks,ntemp = assignment.match()
                utility += utemp
                matchNum += ntemp
            batch.clear()#匹配结束后清空
        # arriveNum += 1 #标记到达了几个众包参与者
    return utility,matchNum

def solve(totalNum):
    memory = resource.getrusage(resource.RUSAGE_SELF)
    avgUtility = 0.0
    avgTime = 0
    avgMemory = 0
    avgMatchNu = 0
    startTime = time.perf_counter()
    avgUtility,avgMatchNu = TGOA_OP(totalNum)
    endTime = time.perf_counter()
    avgTime = endTime - startTime
    avgMemory = memory.ru_maxrss
    # print(avgUtility,avgTime,avgMemory,avgMatchNu)
    return [avgUtility,avgTime,avgMemory,avgMatchNu]
    

def varyWorkers(testNUm):#测试变化的工作者，其余变量保持不变
    fin = open("./result/synthetic/data/varyworkers.txt",'a+',encoding='utf-8')
    for w in  [100, 200, 500, 1000, 5000]:
        fileName = f"./dataset/synthetic/{w}_2500_1_2.0_0.5_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")
        
    #文件关闭
    fin.close()

def varyTasks(testNUm):#测试变化的工作者
    fin = open("./result/synthetic/data/varytasks.txt",'a+',encoding='utf-8')
    for t in   [500, 1000, 2500, 5000, 10000]:
        fileName = f"./dataset/synthetic/500_{t}_1_2.0_0.5_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")
        
    #文件关闭
    fin.close()

def varyCw(testNUm):#测试工作者能力变化的影响
    fin = open("./result/synthetic/data/varycw.txt",'a+',encoding='utf-8')
    for cw in [1, 2, 3, 4, 5]:
        fileName = f"./dataset/synthetic/500_2500_{cw}_2.0_0.5_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")
        
    #文件关闭
    fin.close()

def varyRw(testNUm):#测试工作者半径变化的影响
    fin = open("./result/synthetic/data/varyrw.txt",'a+',encoding='utf-8')
    for rw in [1.0, 1.5, 2.0, 2.5, 3.0]:
        fileName = f"./dataset/synthetic/500_2500_1_{rw}_0.5_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")
        
    #文件关闭
    fin.close()

def varyDw(testNUm):#工作者接受率变化的影响
    fin = open("./result/synthetic/data/varydw.txt",'a+',encoding='utf-8')
    for dw in [0.1, 0.3, 0.5, 0.7, 0.9]:
        fileName = f"./dataset/synthetic/500_2500_1_2.0_{dw}_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def varyDdl(testNUm):#截至时间变化的影响
    fin = open("./result/synthetic/data/varyddl.txt",'a+',encoding='utf-8')
    for ddl in [2, 4, 6, 8, 10]:
        fileName = f"./dataset/synthetic/500_2500_1_2.0_0.5_{ddl}_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def varyPtsNormal(testNUm):#正态分布任务支付大小变化的影响
    fin = open("./result/synthetic/data/varyptsnormal.txt",'a+',encoding='utf-8')
    for pt in [2, 5, 10, 15, 20]:
        fileName = f"./dataset/synthetic/500_2500_1_2.0_0.5_6_{pt}/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def varyPtsExponentail(testNUm):#指数分布任务支付大小变化的影响
    fin = open("./result/synthetic/data/varyptsexponentail.txt",'a+',encoding='utf-8')
    for pt in [2, 5, 10, 15, 20]:
        fileName = f"./dataset/synthetic/500_2500_1_2.0_0.5_6_{pt+100}/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def varyPtsUniform(testNUm):#任务支付大小变化的影响
    fin = open("./result/synthetic/data/varyptsuniform.txt",'a+',encoding='utf-8')
    for pt in [2, 5, 10, 15, 20]:
        fileName = f"./dataset/synthetic/500_2500_1_2.0_0.5_6_{pt+1000}/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def scalability(testNUm):
    fin = open("./result/synthetic/data/scalability.txt",'a+',encoding='utf-8')
    for s in range(1,11):
        w = s*10**3
        t = s*10**4
        fileName = f"./dataset/synthetic/{w}_{t}_1_2.0_0.5_6_10/data_00.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def EverySenderCw(testNUm):#真实数据集
    fin = open("./result/real/data/varyEverysenderCw.txt",'a+',encoding='utf-8')
    for cap in [1,2,3,4,5,6,7,8,9,10]:
        fileName = f"./dataset/real/EverySender_cap{cap}/data_00_time.txt"
        ansList = [0,0,0,0]
        if os.path.exists(fileName):
            workers.clear()
            tasks.clear()
            queue.clear()
            workerNum,taskNum,utilityMax,totalNum = readData(fileName)
            for n in range(testNUm):#测试次数
                ans=solve(totalNum)
                for ansi in range(4):
                    ansList[ansi] += ans[ansi]
            writeStr = "TGOA-OP"
            for result in ansList:
                temp = result/testNUm
                print(temp,end=' ')
                writeStr +=" "+str(temp)
            print()
            writeStr += "\n"
            fin.write(writeStr)
        else:
            print(fileName,"文件不存在")

def  gMissionCw(testNUm):
        fin = open("./result/real/data/varygMissionCw.txt",'a+',encoding='utf-8')
        for cap in [1,2,3,4,5,6,7,8,9,10]:
            fileName = f"./dataset/real/gMission_cap{cap}/data_00_time.txt"
            ansList = [0,0,0,0]
            if os.path.exists(fileName):
                workers.clear()
                tasks.clear()
                queue.clear()
                workerNum,taskNum,utilityMax,totalNum = readData(fileName)
                for n in range(testNUm):#测试次数
                    ans=solve(totalNum)
                    for ansi in range(4):
                        ansList[ansi] += ans[ansi]
                writeStr = "TGOA-OP"
                for result in ansList:
                    temp = result/testNUm
                    print(temp,end=' ')
                    writeStr +=" "+str(temp)
                print()
                writeStr += "\n"
                fin.write(writeStr)
            else:
                print(fileName,"文件不存在")

if __name__ =="__main__":
    testNum = 10
    varyWorkers(testNum)
    varyTasks(testNum)
    varyCw(testNum)
    varyRw(testNum)
    varyDw(testNum)
    varyDdl(testNum)
    varyPtsNormal(testNum)
    varyPtsExponentail(testNum)
    varyPtsUniform(testNum)
    
    scalability(testNum)

    EverySenderCw(testNum)
    gMissionCw(testNum)